1. Field of the Invention
The present invention relates generally to computer-aided design (CAD) applications, and in particular, to a method, apparatus, and article of manufacture for optimizing road design in a CAD application.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.)
Introduction
The geometric design of a road is a crucial part in any highway construction project. Once fixed, the design determines largely the construction costs. Multiple factors determine the construction cost of a road. In [CGF89], Chew et. al. divide construction costs in six major categories, pavement (25%), earthwork (25%, half of this is haul cost), bridges (20%), drainage (10%), miscellaneous items (10%), and land purchase (10%). From this, one may note that earthwork cost is a major cost component in the construction of roads.
The geometric design of a road is traditionally done in two stages: the horizontal alignment design and the vertical alignment design. The horizontal alignment is the road trajectory from a satellite's eye view. The horizontal alignment determines the overall length of the road, and therefore directly affects the pavement cost. Early attempts at horizontal alignment optimization were based on the technique of dynamic programming [Tri87]. More recent approaches use methods similar to genetic algorithms [JS03] or local neighborhood heuristics [LTL09].
For a given horizontal alignment, a vertical alignment, also called vertical road profile, is created with the goal to reduce earthwork cost. The vertical profile can be understood like a scatter plot, where the x-axis represents the distance from the beginning of the road, along the centerline. The y-axis represents the corresponding elevation values. Recorded points are connected by lines (slopes). This renders the road profile piecewise, whose pieces are these linear slopes, or grades of the road. The points that form the intersection of the grades are called the Points of Vertical Intersection (PVI). FIG. 1 illustrates a typical road profile and a corresponding mass diagram underneath, that represents the earthwork volumes. The dotted line on the top of FIG. 1 is the piecewise road profile (f(x)) that is illustrated along with the ground surface (g(x)). The black dots represent the PVIs. In order to provide a smooth ride, vertical curves are placed between the grades at each PVI.
Existing Methods for Design Optimization
An optimal vertical road profile with respect to earthwork cost, tries to follow the ground surface as close as possible. The closer the road is to the ground profile, the less earthwork needs to be done in order to cut or fill sections of the road. However, due to design constraints like grade changes, vertical curve length, etc., it is not always possible to follow the ground surface exactly.
Finding the road profile that minimizes the construction costs, subject to design constraints, is a process referred to as “profile design optimization.”
Traditionally, the design of road profiles is done manually by engineers. In this approach, the vertical profile is evaluated with an integration of the earthwork volumes between the road profile and the ground surface. The integral can be plotted by hand or with the help of software. The plot of the integral is called a mass diagram, and is shown at the bottom of FIG. 1 as the cumulative mass:
      h    ⁡          (      x      )        =                    ∫        0        x            ⁢              f        ⁡                  (          u          )                      -                  g        ⁡                  (          u          )                    ⁢                          ⁢                        ⅆ          u                .            After visual inspection of the mass diagram, the engineer changes the profile and recomputes the volumes. This process is repeated until a satisfying solution is found. This common process therefore uses only the volumes of earth as a measure to quantify a profile.
Using the mass diagram, an experienced engineer is able to produce notably good designs. However, due to timely and budgetary constraints, a final alignment is often chosen from a small selection of possible solutions. Selecting the best of all possible designs can be framed as a multi-level mathematical optimization problem of operations research.
Since the 1980's, research has been done to automate the profile design optimization process with the help of computers. Methodologies and mathematical models were designed to solve the optimization problem. Most approaches to optimize the vertical profile use the mathematical method of linear programming (LP) to solve more or less sophisticated models [Eas88, Mor96, LC01, ASA05, Mor09, KL10]. In contrast to the volume measure approach in the mass diagram, these methods consider also the hauling costs of material. For a given set of PVI's, Easa presented a heuristic to select the elevation of the PVI's, and a LP that computes the earthwork cost for the selection [Eas88]. A similar approach using genetic methodologies and tabu search was shown by Aruga [ASA05]. More incorporated the selection of the elevation directly into the LP [Mor96], which was further developed in [Mor09, KL10]. Lee [LC01] presents a mixed integer linear programming approach that selects the best subset of a fixed set of potential PVI's.
All the prior art methods require the user to provide a fixed set of PVI's. Furthermore, none of the methods optimizes the exact location of the PVI's with respect to elevation and horizontal position. Also, the prior art fails to optimize the length of the vertical curves at each PVI. The methods in [Eas88, Mor96, ASA05, Mor09, KL10] optimize the elevation only and in [LC01], only the best subset of a given set of PVI's is chosen. The prior art methods in [Mor96, Mor09, KL10] use ground elevation information (a ground profile) only along the centerline. They do not support the use of additional ground profile offsets. Ground profile offsets are profiles of the existing ground, that are at an offset distance to the left and right of the original centerline ground profile (e.g. instead of just profiles with elevation points at the centerline, profiles for elevations on the road lanes, or sidewalks, or adjacent slopes may be included).
In view of the above, what is needed is a system and method that optimizes not only the exact location of the PVIs with respect to elevation and horizontal position but also optimizes the length of vertical curves at each PVI.